#pragma once

#include <DirectXMath.h>
#include <vector>
#include <stdlib.h>
#include "LineList.h"
#include "TriangleAccessor.h"

using namespace std;
using namespace DirectX;

class KdTree
{
public:
	struct KD_NODE_t
	{
		KD_NODE_t ();

		enum Dimension{
			x=0, y=1, z=2, none=3
		}						   DIVIDES_BY;			// Axis which has been choosen for spliting
		enum Branch{
			left=0, right=1, root=3
		}						   BRANCH_WAY;			// Is this node in the left or right branch
		float					   SOLE_MEDIAN_VALUE;	// Value of splitting median
		XMFLOAT3				   MEDIAN_CENTROID;		// Centroid of splitting median triangle
		XMFLOAT3				   BB_MIN;				// Lower boundry of subtree
		XMFLOAT3				   BB_MAX;				// Upper boundry of subtree
		XMFLOAT3				   SPLITTING_PLANE[4];	// Splitting plane with 4 corner points
		vector<TriangleAccessor *> STORED_TRI_LIST_ptr;	// Stored triangles as TriangleAccessor pointer if node is a leaf
		KD_NODE_t				  *LEFT_CHILD_ptr,		// Child nodes
								  *RIGHT_CHILD_ptr;
	};

	// Constructor and Destrutor
	KdTree();
	KdTree( int max_tree_depth ):m_MAX_TREE_DEPTH(max_tree_depth) {};

	void DeleteTree_r ( KD_NODE_t *rootNode );
	bool FillLineList ( void );
	LineList* GetLineList(void);

	// KdTree Methods
	KD_NODE_t* MakeTree_r ( vector<TriangleAccessor* > complete_tri_list, KD_NODE_t *prev_node, int current_idx, int length, short split_dimension, int branch, int depth );

	XMFLOAT3 GetUpperRootCentroidBound ( vector<TriangleAccessor *> triangleList );
	XMFLOAT3 GetLowerRootCentroidBound ( vector<TriangleAccessor *> triangleList );
	void GetSubtreeBounds ( KD_NODE_t *current_node, KD_NODE_t *prev_node );

	void GetSplittingPlanePoints ( KD_NODE_t *prev_node, int median, int split_dimension );
	short ChooseSplittingDimension ( KD_NODE_t *prev_node );

	// Comparators for nth_element
	static bool nth_element_comp_X ( TriangleAccessor left, TriangleAccessor right ) { return ( left.GetCentroid().x < right.GetCentroid().x ); }
	static bool nth_element_comp_Y ( TriangleAccessor left, TriangleAccessor right ) { return ( left.GetCentroid().y < right.GetCentroid().y ); }
	static bool nth_element_comp_Z ( TriangleAccessor left, TriangleAccessor right ) { return ( left.GetCentroid().z < right.GetCentroid().z ); }

	// These two methods aren't used anymore since nth_element is faster
	void Quicksort_r( vector<TriangleAccessor *> triangleList, int startIdx, int endIdx, int lookupDimension);
	void SwapValues ( TriangleAccessor &a, TriangleAccessor &b );

	// Ray Intersection Methods
	TriangleAccessor* VisitNodes_r( KD_NODE_t *node, XMFLOAT3 origin_point, XMFLOAT3 ray_vector, float tmax);
	//bool IntersectLineTriangle(TriangleAccessor* t, DirectX::XMVECTOR origin_point, DirectX::XMVECTOR ray_vector);
	bool IntersectLineTriangle(TriangleAccessor* t, XMFLOAT3 origin_point, XMFLOAT3 ray_vector);

private:
	vector<LineVertex> m_LINEVERTEX_LIST;	// List consists of Bounding Box vectors (min and max each);
	LineList *m_LINELIST;
	int m_MAX_TREE_DEPTH;
};